package Tree;
import java.util.LinkedList;
import java.util.Queue;


public class BinaryTree {
	private Node root=null;
	BinaryTree(Object element) {
		root = new Node(element);
	}
	
	public BinaryTree() {
	}

	public void add(Object element) {
		if(root==null) 
		{
			root = new Node(element);
			return;
		}
		Node current=root;
		int hash=element.hashCode();
		while(true) {
		if(hash<current.key)
			if(current.left!=null) current=current.left;
			else
			{
				current.left = new Node(element);
				return;
			}
		else
			if(current.right!=null) current=current.right;
			else
			{
				current.right = new Node(element);
				return;
			}
		}
	}
	
	public void delete(Object element) {
		if(root==null) return;
		int hash=element.hashCode();
		if(root.key==hash)
		{
			if(root.left==null && root.right==null)
				root=null;
			else if(root.left==null) root=root.right;
			else if(root.right==null) root=root.left;
			else 
			{
				Node search=root,parent=null;
				while(search.left!=null) 
				{
					parent=search;
					search=search.left;
				}
				parent.left=search.right;
				search.right=null;
				root=search;
			}
			return;
		}
		if(hash<root.key) delete(hash,root,0);
		else delete(hash,root,1);
	}
	
	public void delete(int hash, Node parent, int way) {
		Node current;
		if(way==0) current=parent.left;
		else current=parent.right;
		if(current==null) return;
		if(current.key==hash)
		{
			if(current.left==null && current.right==null)
				parent=null;
			else if(current.left==null) 
				if(way==0) parent.left=current.right;
				else parent.right=current.right;
			else if(current.right==null)
				if(way==0) parent.left=current.right;
				else parent.right=current.right;
			else 
			{
				Node search=current.right,searchparent=current;
				while(search.left!=null)
				{
					searchparent=search;
					search=search.left;
				}
				searchparent.left=search.right;
				search.right=null;
				if(way==0) parent.left=search;
				else parent.right=search;
				search.left=current.left;
				search.right=current.right;
			}
			return;
		}
		if(current.key<hash) delete(hash,current,0);
		else delete(hash,current,1);
	}
	
	public boolean isNode(Object element) {
		Node current=root;
		int hash=element.hashCode();
		while(current!=null)
		{
			if(hash==current.key) return true;
			if(hash<current.key) current=current.left;
			else current=current.right;
		}
		return false;
	}
	
	public void printHeight() {
		printHeight(root);
		System.out.println();
	}
	public void printWidth() {
		Queue<Node> q = new LinkedList<Node>();
		q.add(root);
		while(q.size()>0)
		{
			Node current=q.poll();
			System.out.print(current.element + " ");
			if(current.left!=null) q.add(current.left);
			if(current.right!=null) q.add(current.right);
		}
		System.out.println();
	}
	
	private void printHeight(Node n) {
		if(n!=null)
		{
			System.out.print(n.element + " ");
			printHeight(n.left);
			printHeight(n.right);
		}
	}
	
	private class Node {
		private Object element;
		private int key;
		private Node left=null,right=null;
		Node(Object element) {
			this.element=element;
			key=element.hashCode();
		} 
	}
}
